package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC377 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int combinationSum4(int[] nums, int target) {
            Arrays.sort(nums);
            int[] dp = new int[target + 1];
            for (int i = 0; i <= target; i++) {
                for (int j = 0; j < nums.length && i - nums[j] >= 0; j++) {
                    if (i == nums[j]) {
                        dp[i] += 1;
                        break;
                    }
                    dp[i] += dp[i - nums[j]];
                }
            }

            return dp[target];
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] nums = InputUtil.toIntegerArray("[1, 2, 3]");
        System.out.println(solution.combinationSum4(nums, 4));
    }

    public static void main(String[] args) throws Exception {
        LC377 an = new LC377();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
